package leetcode;

import util.Tree;
import util.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Project : algorithm-learning-java
 * @Author : Ruoyu Wang
 * @User : Momenta
 * @DateTime : 2024/1/27 11:00
 */
public class Q0173 {
    List<TreeNode> stack = new ArrayList<>();
    List<Integer> f = new ArrayList<>();
    int val = -1;
    int max;

    public Q0173(TreeNode root) {
//    public BSTIterator(TreeNode root) {
        stack.add(root);
        f.add(0);
        TreeNode node = root.left;
        while (node != null) {
            stack.add(node);
            f.add(-1);
            node = node.left;
        }
        node = new TreeNode(-1);
        stack.get(stack.size() - 1).left = node;
        stack.add(node);
        f.add(-1);

        node = root;
        while (node.right != null) {
            node = node.right;
        }
        max = node.val;
    }

    public int next() {
        if (stack.get(stack.size() - 1).right != null) {
            stack.add(stack.get(stack.size() - 1).right);
            f.add(1);
            TreeNode node = stack.get(stack.size() - 1).left;
            while (node != null) {
                stack.add(node);
                f.add(-1);
                node = node.left;
            }
            val = stack.get(stack.size() - 1).val;
            return val;
        }

        while (f.get(f.size() - 1) == 1) {
            f.remove(f.size() - 1);
            stack.remove(stack.size() - 1);
        }

        stack.remove(stack.size() - 1);
        f.remove(f.size() - 1);

        val = stack.get(stack.size() - 1).val;
        return val;
    }

    public boolean hasNext() {
        return val < max;
    }

    public static void main(String[] args) {
        int[] pre = {7, 3, 15, 9, 20};
        int[] in = {3, 7, 9, 15, 20};
        TreeNode root = Tree.createTreeByPreorderAndInorder(pre, in);
        Q0173 sl = new Q0173(root);
        System.out.println(sl.next());
        System.out.println(sl.next());
        System.out.println(sl.hasNext());
        System.out.println(sl.next());
        System.out.println(sl.hasNext());
        System.out.println(sl.next());
        System.out.println(sl.hasNext());
        System.out.println(sl.next());
        System.out.println(sl.hasNext());
    }
}
